

			ARBORE
		       --------

	Se considera un arbore binar de cautare A, avand n noduri continand cheile 1,2,..,n. O per-
mutare p=[p1,p2,..,pn] a numerelor 1,2,..,n se numeste "consistenta" cu arborele A daca arborele
de cautare poate fi construit pornind de la arborele vid prin inserarea numerelor intregi p1,p2,..,
pn in aceasta ordine.
	Sa se determine numarul permutarilor multimii {1,2,..,n} care sunt "consistente" cu arbore-
le dat. (Altfel spus, cate secvente distincte de chei exista pentru ca arborii binari de cautare -
obtinuti prin inserarea cheilor in ordinea data - sa fie identici cu arborele dat ? ).

DATE DE INTRARE:
	Pe prima linie a fisierului "ARBORE.IN" este scris un singur numar natural n (1<=n<=100),
reprezentand numarul de noduri din arbore. Pe cea de a doua linie se afla n numere naturale dis-
tincte, separate printr-un singur spatiu. Aceste numere reprezinta cheile asociate arborelui dat in
preordine. Primul numar este cheia asociata radacinii; este urmata de cheile asociate subarborelui
stang, si de cheile asociate subarborelui drept (de asemenea in preordine).

DATE DE IESIRE:
	Rezultatul se va scrie in fisierul "ARBORE.OUT" si trebuie sa reprezinte numarul permuta-
rilor consistente cu arborele din fisierul de intrare.

ATENTIE: Acest numar poate avea pana la 200 de cifre.

EXEMPLU:
ARBORE.IN		ARBORE.OUT
5			8
2 1 4 3 5

Cele 8 permutari consistente cu arborele dat sunt:
1) 2 1 4 3 5
2) 2 4 1 3 5
3) 2 4 5 3 1
4) 2 4 1 5 3
5) 2 1 4 5 3
6) 2 4 3 1 5
7) 2 1 4 5 3
8) 2 4 3 5 1